﻿namespace AlgLrnLib.Sorting
{
    public class InsertionSort : BaseSort
    {
        #region Public Methods
        public override int[] SortAsc(int[] numbers, DebugTraceDelegate DEBUG_TRACE)
        {
            return Sort(DEBUG_TRACE, numbers);
        }

        public override int[] SortDesc(int[] numbers, DebugTraceDelegate DEBUG_TRACE)
        {
            return Sort(DEBUG_TRACE, numbers, false);
        }
        #endregion

        #region Private Members
        private int[] Sort(DebugTraceDelegate DEBUG_TRACE, int[] numbers, bool asc = true)
        {
            DEBUG_TRACE(numbers, "INITIAL STATE", true); // Clean the GUI and print initial results

            int key = -1;

            for (int j = 1; j < numbers.Length; j++)
            {
                key = numbers[j];
                int i = j - 1;
                while (i >= 0 && Compare(key, numbers[i], asc)) // sort in ascending order
                {
                    numbers[i + 1] = numbers[i]; // numbers[i + 1] is actually numbers[j]
                    i--;

                    DEBUG_TRACE(numbers, string.Format("j = {0}, i = {1}, key = {2}, ITEMS MOVING", j, i, key), false); // Print itteration results to the GUI
                }

                numbers[i + 1] = key; // if the while cycle did not run at all the elements stays where it was

                DEBUG_TRACE(numbers, string.Format("j = {0}, i = {1}, key = {2}, KEY INSERTED", j, i, key), false); // Print itteration result to the GUI
            }

            DEBUG_TRACE(numbers, "FINAL STATE", false); // Print final results to the GUI

            return numbers;
        }
        #endregion
    }
}
